﻿// 0907train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
给你一个包含 n 个整数的数组 nums ，和一个整数 k 
请你找出 长度大于等于 k 且含最大平均值的连续子数组。并输出这个最大平均值
任何计算误差小于 10-5 的结果都将被视为正确答案

示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75000
 */
double findMaxAverage(vector<int>& nums, int k)
{
	//最大平均值，一定处于min(nums)和max(nums)之间
	vector<int>sort_vec = nums;
	sort(sort_vec.begin(), sort_vec.end());
	double left = sort_vec[0], right = sort_vec[sort_vec.size() - 1];

	vector<double>pre_sum(nums.size()+1);
	while (right-left>1e-5)
	{
		double min_sum = 0, mid = left + (right - left) / 2;
		bool is_checked = false;
		for (int i=1; i<=nums.size(); i++)
		{
			pre_sum[i] = pre_sum[i - 1] + (nums[i - 1] - mid);
			if (i>=k)
			{
				//pre_sum[i-k]可能是负数，
				//如果pre_sum[i-k]>0不用管，前i-k个数平均值，肯定大于mid
				min_sum = min(min_sum, pre_sum[i - k]);
			}
			//pre_sum增大，说明i-k到i之间，平均值肯定大于mid
			//也就是说num_vec[i-k+1]-mid>=0，如果不存在，pre_sum肯定不会递增
			if (i>=k && pre_sum[i]> min_sum)
			{
				is_checked = true;
				break;
			}
		}
		//平均值比mid大，缩减mid
		if (is_checked) left = mid;
		else right = mid;
	}
	/*
	 平均值>=mid
	 sum>=mid*n
	 数组里每一个数-mid>=0
	 sums[i-k]等价于0到前i-k个数的和 如果sum[i]-sums[i-k]>0表示有一段大于k的子区间，平均值>=mid
	 */
	return left;
}

/*
 从一个长度为N的正数数组numbers中找出长度至少为L且几何平均值最大的子数组，并输出其位置和大小
 （K个数的几何平均值为K个数的乘积的K次方根）  
若有多个子数组的几何平均值均为最大值，则输出长度最小的子数组  
若有多个长度相同的子数组的几何平均值均为最大值，则输出最前面的子数组。  

输入描述：  
第一行输入为N、L，N表示numbers的大小(1<=N<=100000)，L表示子数组的最小长度(1<=L<=N)  
之后N行表示numbers中的N个数，每个一行(10^-9<=numbers<=10^9)。  

输出描述：  
输出子数组的位置(从0开始计数)和大小，中间用一个空格隔开。  

补充说明：  
用例保证几何平均值为最大值的子数组外，其他子数组的几何平均值至少比最大值小最大值的10^-10倍  

示例1：输入输出示例仅供调试，后台判题数据一般不包含示例  
输入  
3 2  
2  
2  
3  
输出：  
1 2  
说明：  
长度至少为2的子数组有3个，[2,2][2,3][2,2,3]，几何平均值最大为[2,3]，输出其位置1和长度2
 */
class Solution01
{
public:
	bool cal(vector<double>&num_vec, double mid_num, int L)
	{
		//先算出0-L段的
		double result = 1;
		for (int i=0; i<L; i++)
		{
			result *= (num_vec[i]/mid_num);
		}
		//当前mid_num并非最大几何平均值，因为0-L中的数全大于mid_num
		if (result>=1)
		{
			sub_arr_pos = 0;
			sub_arr_size = L;
			return true;
		}

		double pre_result = 1;
		double min_pre_result = DBL_MAX;
		int min_pre_result_pos = 0;

		for (int i=L; i<num_vec.size(); i++)
		{
			result *= (num_vec[i] / mid_num);
			pre_result *= (num_vec[i - L] / mid_num);

			if (pre_result<min_pre_result)
			{
				min_pre_result = pre_result;
				min_pre_result_pos = i - L;
			}



		}

		//
	}

	Solution01(vector<int>&num_vec, int L)
	{
		vector<int>sort_vec = num_vec;
		sort(sort_vec.begin(), sort_vec.end());

		double left = sort_vec[0], right = sort_vec[sort_vec.size() - 1];

		
		while (right-left>pow(10,-10))
		{
			double min_sum = 1, mid = left + (right - left) / 2;


		}


		//Solution01
	}
private:
	int sub_arr_pos = -1, sub_arr_size = 0;
};

class Solution11
{
public:
	Solution11(vector<double>&num_vec, int k)
	{
		vector<double>sort_vec = num_vec;
		sort(sort_vec.begin(), sort_vec.end());

		double left = sort_vec[0], right = sort_vec[sort_vec.size() - 1];

		while (right-left>pow(10,-10))
		{
			//初始化每一轮前缀和pre_sum
			vector<double>pre_sum(num_vec.size() + 1);
			pre_sum[0] = 1;

			double min_prev_sum = 1; //每一轮的最小pre_sum[i-k]
			int min_prev_pos = 0; //每一轮最小i-k的位置
			double mid = left + (right - left) / 2;
			bool is_check = false;//最大平均值是否大于mid

			int curr_sub_pos = -1;
			int curr_sub_length = INT_MAX;

			for (int i=1; i<=num_vec.size(); i++)
			{
				pre_sum[i] = pre_sum[i - 1] * (num_vec[i - 1] / mid);

				if (i>=k)
				{
					if (pre_sum[i-k]< min_prev_sum)
					{
						min_prev_sum = pre_sum[i - k];
						min_prev_pos = i - k; //pre_sum[3]-pre_sum[1]这段数的起始位置就是1
					}
				}
				if (i>=k && pre_sum[i]>= min_prev_sum)
				{
					//当前子数组最大几何平均>mid
					is_check = true;
					//输出长度最小的子数组
					if (i-min_prev_pos < curr_sub_length)
					{
						curr_sub_pos = min_prev_pos;
						curr_sub_length = i - min_prev_pos;
					}
					
				}
			}
			if (curr_sub_pos>-1)
			{
				sub_pos = curr_sub_pos;
				sub_length = curr_sub_length;
			}

			if (is_check)
			{
				//增大mid，在更大范围寻找最大几何平均
				left = mid;
			}
			else
			{
				right = mid;
			}

		}
		//1 2
		//几何平均值最大为[2,3]，输出其位置1和长度2
		cout << sub_pos << ' ' << sub_length;

		//Solution11
	}
private:
	int sub_pos = -1, sub_length = INT_MAX;
};

int main()
{
/*
3 2  
2  
2  
3 
*/
	int v_size, length;
	cin >> v_size >> length;
	cin.ignore();
	vector<double>num_vec(v_size);
	string input;
	for (int i=0; i<v_size; i++)
	{
		getline(cin, input);
		num_vec[i] = stod(input);
	}

	Solution11 solu(num_vec, length);
    
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
